package leetcode.hot100;

@SuppressWarnings("all")
public class _239_滑动窗口最大值 {

    // 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧
    // 你只可以看到在滑动窗口内的 k 个数字，滑动窗口每次只向右移动一位
    // 返回每个滑动窗口中的最大值集合
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return null;
        if (k == 1) return nums;
        // 根据k值可以确定滑动窗口总的数量
        // 如果数组长度为5，k为3，那么总的就有3个滑动窗口
        int slidingNum = nums.length - k + 1;
        int[] result = new int[slidingNum];
        // 可以立马确定第一个滑动窗口的最大值
        int max = nums[0];
        int maxIdx = 0;
        for (int i = 1; i < k; i++) {
            if (nums[i] >= max) {
                max = nums[i];
                maxIdx = i;
            }
        }
        result[0] = max;
        // 由第一个窗口最大值所在的位置推出下一个窗口最大值
        for (int i = 1; i < slidingNum; i++) {
            // 上一个窗口的最大值包含在下一个窗口中，那么只需要用最大值和当前窗口中的最后一个值比较即可
            int last = i + k - 1;
            if (maxIdx >= i) {
                if (max <= nums[last]) {
                    max = nums[last];
                    maxIdx = last;
                }
                // 记录
                result[i] = max;
                continue;
            }
            // 上一个窗口的值对于当前窗口没有参考意义了，那么需要重新初始化当前窗口最大值
            max = nums[i];
            for (int j = i + 1; j <= last; j++) {
                if (max <= nums[j]) {
                    max = nums[j];
                    maxIdx = j;
                }
            }
            result[i] = max;
        }
        return result;
    }
}
